package skiplist;

// SkipList工具类
public class SkipListUtil {

    // 静态常量
    public static final int ZSKIPLIST_MAXLEVEL = 32;
    public static final double ZSKIPLIST_P = 0.25;

    // 随机层数函数
    public static int zslRandomLevel() {
        int level = 1;
        while (Math.random() < ZSKIPLIST_P) {
            level++;
        }
        return level < ZSKIPLIST_MAXLEVEL ? level : ZSKIPLIST_MAXLEVEL;
    }

    // 跳跃表节点创建
    public static skiplist.SkipListNode zslCreateNode(int level, int score, String val) {
        skiplist.SkipListNode zn = new skiplist.SkipListNode(level);
        zn.score = score;
        zn.val = val;
        return zn;
    }

    // 跳跃表创建
    public static skiplist.SkipList zslCreate() {
        int j;
        skiplist.SkipList zsl = new skiplist.SkipList();

        zsl.level = 1;
        zsl.length = 0;
        zsl.header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, null);
        for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
            zsl.header.levels[j].forward = null;
            zsl.header.levels[j].span = 0;
        }
        zsl.header.backward = null;
        zsl.tail = null;

        return zsl;
    }

    // 打印跳表
    public static void zslPrint(skiplist.SkipList zsl) {
        String [] zslPrintArr = new String[zsl.level];
        int i;
        for (i = zslPrintArr.length - 1; i >= 0; i--) {
            zslPrintArr[i] = "";
        }
        skiplist.SkipListNode x= zsl.header.levels[0].forward;
        while (x != null) {
            String temp = "(" + x.score + "," + x.val + ")" + " ";
            for (i = 0; i < x.levels.length; i++) {
                zslPrintArr[i] += temp;
            }
            for (i = x.levels.length; i < zsl.level; i++) {
                for (int j = 0; j < temp.length(); j++) {
                    zslPrintArr[i] += " ";
                }
            }
            x = x.levels[0].forward;
        }
        for (i = zslPrintArr.length - 1; i >= 0; i--) {
            System.out.println(zslPrintArr[i]);
        }
        System.out.println();
    }

    // 查找
    public static skiplist.SkipListNode zslFind(skiplist.SkipList zsl, int score) {
        if (zsl.length == 0) return null;
        skiplist.SkipListNode x, pre;
        x = zsl.header;
        int i, level;
        i = zsl.level - 1;
        while (i >= 0) {
            pre = x.levels[i].forward;
            if (pre.score == score) {
                return pre;
            }
            if (pre.levels[i].forward == null || pre.score > score) {
                i--;
                continue;
            }
            if (pre.score < score) {
                x = pre;
                continue;
            }
        }
        return null;
    }

    // 插入
    public static skiplist.SkipListNode zslInsert(skiplist.SkipList zsl, int score, String val) {
        // 先进行查重
        skiplist.SkipListNode x;
        x = zslFind(zsl, score);
        if (x != null) {
            x.val = val;
            return x;
        }
        skiplist.SkipListNode[] update = new skiplist.SkipListNode[ZSKIPLIST_MAXLEVEL];
        int[] rank = new int[ZSKIPLIST_MAXLEVEL];
        int i, level;

        x = zsl.header;
        for (i = zsl.level - 1; i >= 0; i--) {
            rank[i] = i == zsl.level - 1 ? 0 : rank[i + 1];
            while (x.levels[i].forward != null && (x.levels[i].forward.score < score ||
                    (x.levels[i].forward.score == score &&
                            x.levels[i].forward.val.compareTo(val) < 0))) {
                // 记录各层x前一个节点的索引跨度
                rank[i] += x.levels[i].span;
                // 查找一下个节点
                x = x.levels[i].forward;
            }
            // 记录各层x的前置节点
            update[i] = x;
        }
        // 获取当前节点的level
        level = zslRandomLevel();
        // 如果level大于当前skiplist的level将大于部分的header初始化
        if (level > zsl.level) {
            for (i = zsl.level; i < level; i++) {
                rank[i] = 0;
                update[i] = zsl.header;
                update[i].levels[i].span = zsl.length;
            }
            zsl.level = level;
        }
        // 创建新节点
        x = zslCreateNode(level, score, val);
        for (i = 0; i < level; i++) {
            // 建立x节点索引
            x.levels[i].forward = update[i].levels[i].forward;
            // 将各层x的前置节点的后置节点置为x
            update[i].levels[i].forward = x;
            // 计算x节点各层索引跨度
            x.levels[i].span = update[i].levels[i].span - (rank[0] - rank[i]);
            // 计算x前置节点的索引跨度
            update[i].levels[i].span = (rank[0] - rank[i]) + 1;
        }
        // 如果level小于zsl的level
        for (i = level; i < zsl.level; i++) {
            // 将x前置节点的索引跨度加一
            update[i].levels[i].span++;
        }
        // 设置x前置节点
        x.backward = (update[0] == zsl.header) ? null : update[0];
        // 设置x后面节点的前置节点
        if (x.levels[0].forward != null) {
            x.levels[0].forward.backward = x;
        } else {
            zsl.tail = x;
        }
        // length++
        zsl.length++;

        return x;
    }

    // 删除
    public static void zslDeleteNode(skiplist.SkipList zsl, int score) {
        skiplist.SkipListNode x, pre;
        x = zslFind(zsl, score);
        if (x == null) {
            System.out.println("不存在");
            return;
        }
        x = zsl.header;
        int i;
        for (i = 0; i < zsl.level - 1; i++) {
            while (x.levels[i].forward != null) {
               pre = x.levels[i].forward;
               if (pre == null) break;
               if (pre.score == score) {
                   x.levels[i].forward = pre.levels[i].forward;
                   return;
               }
               x = pre;
            }
        }
        zsl.length--;
    }
}
